#ifndef __DICT_SORTED_VECTOR_HH__
#define __DICT_SORTED_VECTOR_HH__

#include <vector>
#include <algorithm>
using namespace std;

template <class P>
struct K_less {
  bool operator()(const P& l, const P& r) const {
    return l.first < r.first;
  }
};

template <class K, class V>
class DictSortedVector
{
public:
  typedef vector<pair<K, V> > vs_t;

  size_t size() const { return vs.size(); }

  V& operator[](size_t key_index) {
    return vs[key_index].second;
  }
  
  const V& operator[](size_t key_index) const {
    return vs[key_index].second;
  }

  const K& key_at(size_t key_index) const {
    return vs[key_index].first;
  }

  bool find(const K& key, size_t* key_index) const {
    K_less<pair<K, V> > k_less;
    pair<K, V> pp; pp.first = key;
    typename vs_t::const_iterator it = lower_bound(vs.begin(), vs.end(),
						   pp, k_less);
    if (it == vs.end() || (*it).first != key) {
      return false;
    }
    if (key_index) *key_index = it - vs.begin();
    return true;
  }

  bool add(const K& key, const V& value) {
    K_less<pair<K, V> > k_less;
    pair<K, V> pp; pp.first = key;
    typename vs_t::iterator it = lower_bound(vs.begin(), vs.end(), 
					     pp, k_less);
    if (it != vs.end() && (*it).first == key) {
      return false;
    }
    vs.insert(it, make_pair(key, value));
    return true;
  }
  
  void remove(size_t key_index) {
    vs.erase(vs.begin() + key_index);
  }

 private:
    vs_t vs;
};

#endif
